package top.zz;

import java.util.Arrays;

/**
 * 
 * @author jenny
 *
 */
public class SortTest {

	public static void main(String[] args) {
		int[] arrays = { 9, 1, 2, 8, 3, 7, 4, 6, 5 };
		Sort bubbleSort = new Sort(arrays);
		bubbleSort.shellKnuthSort();
	}
}

class Sort {

	int[] arrays;

	public Sort(int[] arrays) {
		this.arrays = arrays;
	}

	public void bubblesort() {
		int temp = 0;
		boolean flag;
		for (int i = 0; i < arrays.length; i++) {
			flag = true;
			for (int j = 0; j < arrays.length; j++) {
				if (j == arrays.length - 1) {
					continue;
				}

				if (arrays[j] > arrays[j + 1]) {
					temp = arrays[j];
					arrays[j] = arrays[j + 1];
					arrays[j + 1] = temp;
					flag = false;
				}
			}
			if (flag) {
				break;
			}
			System.out.println("第" + (i + 1) + "次 ");

			display();
		}

	}

	public void chioceSort() {
		int temp;
		int min = 0;
		for (int i = 0; i < arrays.length; i++) {

			for (int j = i + 1; j < arrays.length - 1; j++) {
				if (arrays[min] > arrays[j]) {
					min = j;
				}
			}

			if (i != min) {
				temp = arrays[i];
				arrays[i] = arrays[min];

				arrays[min] = temp;
			}
			System.out.print("第" + (i + 1) + "轮排序后的结果为:");
			display();
		}
	}

	public void insertSort() {
		for (int i = 0; i < arrays.length; i++) {
			int temp = arrays[i];
			int j = i;
			while (j > 0 && temp < arrays[j - 1]) {
				arrays[j] = arrays[j - 1];
				j--;
			}

			arrays[j] = temp;
			System.out.print("第" + (i + 1) + "轮排序后的结果为:");
			display();
		}
	}

	public void shellKnuthSort() {
		int[] array = arrays;
		System.out.println("原数组为" + Arrays.toString(array));
		int step = 1;
		int len = array.length;
		while (step <= len / 3) {
			step = step * 3 + 1;// 1,4,13,40......
		}
		while (step > 0) {
			// 分别对每个增量间隔进行排序
			for (int i = step; i < len; i++) {
				int temp = array[i];
				int j = i;
				while (j > step - 1 && temp <= array[j - step]) {
					array[j] = array[j - step];
					j -= step;
				}
				array[j] = temp;
			} // end for
			System.out.println("间隔为" + step + "的排序结果为" + Arrays.toString(array));
			step = (step - 1) / 3;
		} // end while(step>0)

		System.out.println("最终排序：" + Arrays.toString(array));
	}

	public void display() {

		for (int i : arrays) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	@SuppressWarnings("unused")
	private Object getValue(int index) {

		return arrays[index];
	}
}